Wireless Communications
Wireless communications devices allow a degree of convenience and mobility that wired devices cannot match. However, wireless communications systems are subject to problems that do not occur to the same degree for wired systems. Foremost among these problems is fading. Fading is the time-variation of channel conditions. A second problem is interference between multiple signals that concurrently use the same part of the frequency spectrum.
As the transmission rate of wireless communications continues to increase, the frequency selectivity of the wireless channel is a major issue. A ‘frequency-selective’ channel is one for which the propagation is a strong function of frequency within the bandwidth of the channel.
Orthogonal Frequency Division Multiplexing (OFDM)
One popular method to deal with frequency-selective channels is orthogonal frequency division multiplexing (OFDM). OFDM is used in wireless local area networks, as covered in the IEEE 802.11a, 802.11g, and 802.11n standards, as well as fixed wireless access systems, as covered in the IEEE 802.16 standards, and high mobility systems for high data rates, as covered in the IEEE 802.20 standards. Anticipated fourth generation cellular telephone systems are also expected to use OFDM.
The basic principle of OFDM is to partition a frequency-selective wide-band channel into a number of parallel, narrow-band sub-channels, also called ‘sub-carriers’, or ‘tones’. Each sub-channel is frequency-nonselective, i.e., non-delay-dispersive. This principle is similar to traditional frequency division multiple access (FDMA). There are, however, major differences between OFDM and FDMA. In OFDM, the frequencies of the sub-channels are spaced as close as possible, without causing mutual interference, i.e., each sub-channel is located in the spectral nulls of the adjacent sub-channels. In OFDM, the conversion to parallel sub-channels can be done digitally, by means of a fast Fourier transform (FFT). In OFDM, a guard interval in the form of a ‘cyclic prefix’, ensures that even in the presence of a residual delay dispersion, the sub-channels do not interfere with each other, as long as the delay spread of the channel is shorter than the duration of the cyclic prefix.
A discrete-time effective channel model for a system using OFDM is given by the following system of equations. The symbol encoded by the OFDM system on the lth sub-channel at discrete time t is denoted by xl[t]. The corresponding received symbols yl[t] after being processed by the OFDM system are given byyl[t]=Hl[t]xl[t]+nl[t].  (1)
Here, Hl[t] is a random variable called the attenuation or ‘fading’ factor for the lth sub-channel at time t. The noise nl[t] is a zero-mean random variable chosen from a Gaussian distribution. The symbols xl[t] and yl[t], the attenuation factor Hl[t], and the noise nl[t] are all represented as complex numbers.
The ‘equalization’ of OFDM systems is simple. Because each sub-channel is effectively narrow-band, the signal received for this sub-channel needs only to be divided by the complex number Hl[t] representing the attenuation at this specific sub-carrier.
Models for Fading and Interference
Depending on the specific application, different probability distributions are appropriate for the random variables Hl[t]. If the variables Hl[t] are selected from a complex Gaussian distribution with zero mean, then the model is called a ‘Rayleigh’ fading model. Rayleigh fading models are very popular models for wireless channels.
If the Hl[t] for the same sub-carrier at neighboring discrete times are correlated, then the model is called a ‘slow-fading’ channel. If the Hl[t] for the same sub-carrier at neighboring discrete times are independent, then the model is called a ‘fast-fading’ channel.
A simplified model for interference is obtained using an ‘erasure’ model for the probability distribution of Hl[t]. In this model, each fading factor Hl[t] is independently selected to be one, with a probability 1-pe, and zero, with a probability pe. The zeros represent interference caused by other signals that occur with probability pe.
Lack of Frequency Diversity in OFDM
Unfortunately, each sub-channel in an OFDM system is effectively narrowband. Therefore, OFDM, by itself, does not give any frequency diversity when a sub-carrier is in a fading dip or an erasure. If Hl[t] has a small magnitude, then its signal-to-noise-ratio (SNR) is low, and the corresponding received symbol is decoded with a high probability of error.
This problem can be solved in several possible ways. First, if the instantaneous SNR for each sub-carrier is known at the transmitter, then adaptive modulation, in combination with appropriate codes, can ensure that the signaling rate for each specific sub-carrier is at an appropriate level that can be sustained without too many errors. Second, if the transmission of the data occurs over a time duration that is much longer than the coherence time of the channel, then appropriate codes combining symbols at the same sub-carrier but over different times can exploit the changes over time in the channel conditions. Third, error-correcting codes can be used across different sub-carriers at the same time. This very common approach is called ‘coded’ OFDM.
However, there are many practical situations where none of the above approaches is optimal, or even possible. The first approach requires instantaneous channel state information at the transmitter, which imposes a large feedback overhead, as well as a large modulation alphabet, which imposes hardware constraints. The second approach requires coding over a long time, which is not desirable in many cases, particularly when long delays cannot be tolerated. Furthermore, long period encoding may be impossible in situations where there is insufficient time diversity, such as in fixed wireless access. Encoding across frequency using an error-correcting code often requires the use of low code-rate codes in order to be effective. That means that an excessive number of redundant symbols are transmitted, decreasing the effective throughput on the channel.
MC-CDMA
For these reasons, another approach called ‘multi-carrier code division multiple access’ (MC-CDMA) can be used, see K. Fazel, “Performance of CDMA/OFDM for Mobile Communications Systems,” ICUPC 1993, vol. 2, pp. 975-979, 1993, and S. Kaiser, “Trade-off Between Channel Coding and Spreading in Multi-carrier CDMA Systems,” Proc. ISSSTA 1996, pp. 1366-1370, 1996. In that approach, a data block, on different sub-channel frequencies, is multiplied by a Walsh-Hadamard transform (WHT). This multiplication spreads the information for each symbol over all available tones. The number of symbols that are multiplied is the same as the number of tones, giving a code-rate of one, so that no redundancy is introduced. Because all symbols are transmitted on all tones simultaneously, the system fully exploits the frequency diversity in all channels. Even if some tones are in fading dips, the information from the ‘good’ tones is sufficient to allow reconstruction of the transmitted symbols, in most, but not all cases.
MC-CDMA can be used in ordinary OFDM systems or in coded OFDM systems. When used with coded OFDM systems, the idea is to reduce the redundancy needed in the error-correcting code.
FIG. 1 shows a prior art transmitter or ‘encoder’ 100 for a coded OFDM system using multi-carrier CDMA. Data bits 101 emitted by a source are encoded 110 using an error-correcting code, and thus redundant bits are added to make code words 102. The resulting code words 102 are mapped 120 into a block of complex symbols 103. In the MC-CDMA part of the transmitter, the resulting block of complex symbols are multiplied by a WHT matrix 130 to obtain an equal-length block of complex symbols 104. The resulting equal-length block of symbols is converted 140 into a continuous-time signal 105 in the OFDM part of the transmitter by adding a cyclic prefix and applying an inverse FFT.
The functions of the MC-CDMA part of the transmitter can be expressed as follows. The input at discrete time t is a data block of complex symbols {ul[t]}, and the number of sub-channels N is equal to some power of two. To obtain the block of complex symbols {xl[t]} that is sent to the inverse FFT, we multiply by the N×N WHT matrix WN:
                                          x            l                    ⁡                      [            t            ]                          =                              ∑                          m              =              1                        N                    ⁢                                          ⁢                                    W              lm              N                        ⁢                                                            u                  m                                ⁡                                  [                  t                  ]                                            .                                                          (        2        )            
Walsh-Hadamard Transform Matrices
WHT matrices can be constructed recursively as follows. The smallest version is a 2×2 matrix W2 of the form
                              W          2                =                              1                          2                                ⁢                                    (                                                                    1                                                        1                                                                                        1                                                                              -                      1                                                                                  )                        .                                              (        3        )            
To construct a larger WHT matrix WN, where N=2B, one forms a Kronecker product of B 2×2 WHT matrices. Thus, the WHT matrix W4 is given by W4=W2{circle around (×)}W2, and W8=W2{circle around (×)}W2{circle around (×)}W2, and so on. The expression ‘W2{circle around (×)}M’ means that one expands every l in the matrix M into a sub-matrix W2, and every −l into a sub-matrix −W2. Thus, for example, the next two WHT matrices after W2 are
                                          W            4                    =                                    1              2                        ⁢                          (                                                                    1                                                        1                                                        1                                                        1                                                                                        1                                                                              -                      1                                                                            1                                                                              -                      1                                                                                                                                  -                      1                                                                                                  -                      1                                                                            1                                                        1                                                                                                              -                      1                                                                            1                                                        1                                                                              -                      1                                                                                  )                                      ⁢                                  ⁢        and                            (        4        )                                          W          8                =                              1                          8                                ⁢                                    (                                                                    1                                                        1                                                        1                                                        1                                                        1                                                        1                                                        1                                                        1                                                                                        1                                                                              -                      1                                                                            1                                                                              -                      1                                                                            1                                                                              -                      1                                                                            1                                                                              -                      1                                                                                                                                  -                      1                                                                                                  -                      1                                                                            1                                                        1                                                                              -                      1                                                                                                  -                      1                                                                            1                                                        1                                                                                                              -                      1                                                                            1                                                        1                                                                              -                      1                                                                                                  -                      1                                                                            1                                                        1                                                                              -                      1                                                                                                                                  -                      1                                                                                                  -                      1                                                                                                  -                      1                                                                                                  -                      1                                                                            1                                                        1                                                        1                                                        1                                                                                                              -                      1                                                                            1                                                                              -                      1                                                                            1                                                        1                                                                              -                      1                                                                            1                                                                              -                      1                                                                                                            1                                                        1                                                                              -                      1                                                                                                  -                      1                                                                                                  -                      1                                                                                                  -                      1                                                                            1                                                        1                                                                                        1                                                                              -                      1                                                                                                  -                      1                                                                            1                                                                              -                      1                                                                            1                                                        1                                                                              -                      1                                                                                  )                        .                                              (        5        )            
Factor Graph Representations of Fast Walsh-Hadamard Transforms
Naively, a multiplication using a WHT matrix as in equation (2) appears to require approximately N2 computations. However, the multiplication can be done in a ‘fast’ way requiring on the order of N log2 N operations. The ‘fast’ Walsh-Hadamard transform is analogous to a FFT.
To explain the fast WHT, it is easiest to use a ‘factor graph’. For a detailed explanation of factor graphs, see F. R. Kschischang, B. J. Frey, and H-A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Transactions on Information Theory, vol. 47, pp. 498-519, February 2001. There are several essentially equivalent forms of factor graphs. The following discussion is based on so-called ‘normal’ factor graphs, as described by G. D. Forney, Jr., “Codes on Graphs: Normal Realizations,” IEEE Transactions on Information Theory, vol. 47, pp. 520-548, February, 2001.
A normal factor graph is drawn as a collection of connected vertices. The connections between the vertices, which are drawn as lines, represent ‘variables’. The vertices, which are drawn as squares and referred to as ‘factor nodes’ represent constraints placed on the variables that connect to that factor node. In a ‘normal’ factor graph, each variable can be connected to either one or two factor nodes, and each factor node can connect to one or more variables.
The factor graph for a fast Walsh-Hadamard transform can be constructed using ‘butterfly’ factor nodes, as described by J. S. Yedidia, “Sparse Factor Graph Representations of Reed-Solomon and Related Codes,” MERL TR2003-135, Mitsubishi Electric Research Laboratories, Cambridge, Mass., December, 2003, and Proceedings of the 2003 DIMACS Workshop on Algebraic Coding Theory, September 2003. A butterfly factor node has two ‘input’ variables entering the node from the left, and two ‘output’ variables exiting the node from the right.
In a butterfly factor node, there are two constraints on the variables. The two input variables are denoted by x1 and x2, and the two output variables are denoted by y1 and y2. The two constraints are written asy1=Ax1+Bx2  (6)y2=Cx1+Dx2  (7)where A, B, C, and D are constants. The choice of the four constants in these equations defines the specific form of a butterfly factor node.
As shown in FIG. 2, a prior art butterfly factor node 201 is drawn as a square with the four constraint constants (A, B, C, D) placed inside the node, and with the input variables 211 represented by connected lines coming into the square from the left, and the output variables 212 represented by connected lines coming out of the square to the right. The prototypical butterfly factor node 201 corresponds to equations (6) and (7) above.
FIG. 3 shows a prior art factor graph 300 for a fast Walsh-Hadamard transform of size N=8. The factor graphs for the fast Walsh-Hadamard transforms is constructed using butterfly factor nodes 301 where the constants are given by A=B=C=1/√{square root over (2)}, and D=−1/√{square root over (2)}. The factors are connected in a regular way that is identical to the wiring in FFTs. The input variables 302 on the left are the variables um, the output variables 303 on the right are the variables xl, and the factor graph implements the relationship
                              x          l                =                              ∑                          m              =              1                        N                    ⁢                                          ⁢                                    W              lm              N                        ⁢                                          u                m                            .                                                          (        8        )            
OFDM Receivers
FIG. 4 shows a conventional receiver (decoder) 400 for a prior art coded OFDM system that uses MC-CDMA. The receiver 400 takes the received signal 401, and then in step 410, performs an FFT and removes the cyclic prefix to obtain a block of corrupted complex symbols 402. Then, an inverse WHT is performed 420 to recover complex symbols 403. Finally, complex symbols are decoded 430 using an error-correcting code to obtain a reconstruction 404 of the original transmitted bits.
There are two main problems in the decoders for systems that use MC-CDMA. One is related to the performance when simplified decoding methods are used. The simplest decoding approach is to multiply the received signal with the inverse of the Walsh-Hadamard matrix after equalization of each OFDM tone, and before demodulation and decoding. Unfortunately, this decoding approach leads to noise enhancement. The noise from the ‘bad’ tones with a low SNR, which are amplified in the equalization process, is distributed over all tones. This problem can in principle be solved using maximum-likelihood or optimal detection for the inverse WHT. However, processing-time considerations limit maximum-likelihood detection to very small Walsh-Hadamard matrices.
The second problem with MC-CDMA systems using Walsh-Hadamard transforms is related to the performance of decoding in the presence of many sub-channel ‘erasures’ due to bad SNRs, as may be created by fading dips or interference on channels. Unfortunately, because of the form of the WHT matrix, several different bit combinations can lead to the same complex symbol being transmitted on a single tone. As a simple example, suppose that a 2×2 WHT matrix is used, and the possible input symbols are 1.0 and −1.0. The first output symbol after a Walsh-Hadamard transform is the sum of the two inputs divided by √{square root over (2)}. If the first output symbol is received as a 0.0, then that symbol could have arisen because the first input was a 1.0 and the second input was a −1.0, or vice versa. Naturally, the combination of the information of all tones is sufficient for a demodulation. However, if some tones are erased, then the reconstruction 404 can be ambiguous when a Walsh-Hadamard transform is used. Therefore, it is desired to use a different spreading transform for which an unambiguous choice of the reconstruction can be made so long as at least one output symbol is received correctly.
Asymmetrical Spreading Transforms
For the particular case of a 2×2 spreading matrix, it is known that a considerable performance improvement can be realized by using an asymmetrical spreading matrix of the form
  U  =            (                                    2                                1                                                              -              1                                            2                              )        .  This spreading matrix enforces a transmit symbol constellation that enables reconstruction even if one of the two tones that carry the information about one bit is erased.
A similar idea is described for a transform that spreads symbols across time or space with different transmitting antennas using ‘permutation codes’, S. Tavildar and P. Viswanath, “Permutation Codes: Achieving the Diversity-Multiplexing Tradeoff”, International Symposium on Information Theory (ISIT), Jun. 27, 2004.
However, the prior art transforms are only described for very small N. The only explicit constructions are for cases when the number of sub-carriers is two. It is well known that larger values of N are necessary to obtain a diversity gain that is possible by spreading out a symbol over many different sub-carriers.
To summarize, prior art methods exist for spreading symbols across multiple sub-carriers using a WHT. All of those methods suffer from two problems. There is ambiguity during the decoding when some of the sub-carriers are in deep fades. Noise from faded sub-carriers is amplified when simple decoding methods are used. Some prior art methods spread a symbol across two sub-carriers in a way that can be disambiguated, even if one of the sub-carriers is erased. However, there are no prior art methods for spreading symbols across more than two channels without suffering from the problem of ambiguity when some of the sub-carriers are in deep fades.
Therefore, it is desired to provide a method for spreading symbols to be transmitted over more than two sub-carriers subject to fading, interference, and noise, so that it is possible to reconstruct the symbols unambiguously symbols for MC-CDMA in OFDM systems. There is a similar need for spreading symbols across time-division multiple access (TDMA) or across multiple receive antenna and multiple transmit antenna (MIMO) systems.
In general, it is desired to provide a signal encoding method that is effective for any channel model that can be written in a form similar to that given in equation (1), where the indices l and t represent alternative sub-channels over which symbols are transmitted.